1. Field of the Invention
The present invention relates to a method for constructing a finite-state machine which is utilized for an automatic control system operated according to outside conditions and used in a chemical plant, a power plant, an airplane, a robot and a radar system and relates to a method for constructing a pattern-matching machine obtained by specializing the finite-state machine which is utilized for a retrieving apparatus and an editing machine using a computer pattern matching. Also, the present invention relates to a method for transforming failure transitions of the finite-state machine according to a failure function into a success transition according to a success function and a method for transforming failure transitions of the pattern-matching machine according to a failure function into a success transition according to a success function.
2. Description of the Prior Art
2.1. Previously Proposed Art
A concept of a finite-state machine proposed by McCulloch and Pitts in 1943 has been extended by many researchers, and various characteristics of the finite-state machine has been clarified. The finite-state machine has been recently utilized for the research and development in the industrial world and an academic society as the most simple model of an automaton and a computer. Also, the relationship between the finite-state machine and a regular expression relating to the finite-state machine in a pair has been profoundly researched. The finite-state machine or a finite-state automaton classified as a type of finite-state machine and the regular expression have been reported in various publications and literatures such as a first publication--M. L. Minsky, "Computation: Finite and Infinite Machines", Englewood, N.J., (1967)--, a second publication--E. J. Hopcroft, and D. J. Ullman, "Formal Languages and their Relation to Automata", Addison-Wesley, Mass., (1964)--, a third publication--translation by Nozaki et al., "Language Theory and Automa", Science Inc., (1971)--, a fourth publication--A. Salommaa, "Theory of Automata", Pergamon Press, England, (1969)--, a fifth publication--translated by Kitagawa et al., "Theory of Automata", Kyoritsu Press. (1964)--, a sixth publication--E. Tomira and T. Yokomori "Automata and Theory of languages", Morikita Press, (1992)--, and a literature--R. Mcnaughton and H. Yamada, "Regular Expressions and State Graphs for Automata", IRE Transactions on Electronic Computers", (1960). Therefore, introductory explanation of the finite-state machine and various concepts accompanying the finite-state machine is omitted, and formal definitions of a nondeterministic Moore machine NMO, a deterministic Moore machine DMO, regular expressions relating to the machines NMO and DMO and regular transformations equivalent to the extension of the regular expressions are merely described.
The nondeterministic Moore machine is initially described.
The nondeterministic Moore machine NMO=(Q,.SIGMA.,.DELTA.,.delta.,.lambda.,q) representing a nondeterministic finite-state machine consists of a finite set Q of states, a finite input set .SIGMA. expressed by symbolizing an input from the outside, a finite output set .DELTA. expressed by symbolizing an output to the outside, a state-transition function .delta.(p,.alpha.) designated by a current state p .epsilon. Q of the nondeterministic Moore machine NMO and an input .alpha. .epsilon. .SIGMA. given from the outside for assigning a set of next states to which the nondeterministic Moore machine NMO is transferred in a next time, an output function .lambda.(p') designated only by a next state p' .epsilon. Q for determining a value output to the outside while the state transition to the next state p' is performed, and an initial state q .epsilon. Q. The next states are necessarily determined by values .delta.(p,.alpha.) of the function .delta. for all inputs .alpha., so that the function .delta. is called a total function.
In the above formal definition of the nondeterministic Moore machine NMO, an input .alpha. given from the outside takes states of the machine NMO from a set {p1,p2, - - - ,pN} of current states (or, initially equivalent to a set {q} of the initial states q) to a set .delta.(p1,.alpha.) U--U .delta.(pN,.alpha.) of next states, and the operation that a value {.lambda.(x).vertline.x.epsilon. .delta.(p1,.alpha.) U--U .delta.(pN,.alpha.)} is output is repeated at the same time with each of the state transitions. Here, .delta.(pi,.alpha.) U .delta.(pj,.alpha.) denotes a union of .delta.(pi,.alpha.) and .delta.(pj,.alpha.). Also, even though any input .alpha. is given to the machine NMO from the outside, a state transition from the empty set .phi..OR right.Q to the empty set .phi. is performed in the machine NMO, and an output is equal to the empty set .phi..
Though the state-transition function .delta.(p,.alpha.) is the total function, there is a case that a value of the state-transition function .delta.(p,.alpha.) is equal to that of the empty set .phi.. Therefore, there is a case that the set .delta.(p1,.alpha.) U--U .delta.(pN,.alpha.) of next states transferred from the current states is equal to the empty set .phi.. In this case, current states newly determined are maintained in a state of the empty set .phi. according to the above regulation.
Next, the deterministic Moore machine is described.
The deterministic Moore machine DMO=(Q,.SIGMA.,.DELTA.,.delta.',.lambda.,q) representing a deterministic finite-state machine consists of a finite set Q of states, a finite input set .SIGMA. expressed by symbolizing an input from the outside, a finite output set .DELTA. expressed by symbolizing an output to the outside, a state-transition function .delta.'(p,.alpha.) that assigns to a current state p .epsilon. Q of the deterministic Moore machine DMO and input .alpha. .epsilon. .SIGMA. given from the outside pair a next state to which the deterministic Moore machine DMO is transferred in a next time, an output function .lambda.(p'), depending only the next state p' .epsilon. Q translated, that determines a value output to the outside while the state transition is performed, and an initial state q .epsilon. Q. The next state are necessarily determined by values .delta.'(p,.alpha.) of the function .delta.' for all inputs .alpha., so that the function .delta.' is called a total function.
In the above formal definition of the deterministic Moore machine DMO, an input .alpha. given from the outside takes a state of the machine DMO from a current state p (or, initially equivalent to the initial state q) to a next state .delta.'(p,.alpha.), and the operation that a value .lambda.(.delta.'(p,.alpha.)) is output to the outside is repeated at the same time with each of the state transitions.
Because the state-transition function .delta.'(p,.alpha.) is the total function having an element p of the finite set Q, there is no case that a value of the state-transition function .delta.'(p,.alpha.) is equal to that of the empty set .phi..
Finally, the definition of the regular expression is described.
In cases where a finite set of character strings is expressed by .SIGMA., each of regular expressions on the finite set .SIGMA. denotes a character string on the finite set .SIGMA. defined according to following seven definitions. In this case, the empty character string having a length of zero is included in the finite set of character strings. In detail,
(1) In a first definition, a symbol .phi. is a regular expression which denotes the empty set of character string on the finite set .SIGMA..
(2) In a second definition, a symbol .epsilon. is a regular expression which denotes a set of character strings having a length of zero on the finite set .SIGMA..
(3) In a third definition, a symbol a is a regular expression which denotes a set {.alpha.} (or expressed by .alpha. .epsilon. .SIGMA.) on the finite set .SIGMA..
(4) In a fourth definition, symbols R, S are respectively a regular expression on the finite set .SIGMA., a symbol (R+S) is a regular expression denoting a set {t.vertline.t is an element of a set expressed by R or is an element of a set expressed by S}.
(5) In a fifth definition, symbols R, S are respectively a regular expression on the finite set .SIGMA., a symbol (RS) is a regular expression denoting a set {rs.vertline.r is an element of a set expressed by R and s is an element of a set expressed by S}.
(6) In a sixth definition, a symbol R is a regular expression on the finite set .SIGMA., a symbol (R*) is a regular expression equivalent to another regular expression (--((.epsilon.+R)+(RR))+(RRR))+--).
(7) In a seventh definition, any other symbols not defined by one of the first to sixth definitions are not the regular expression. Also, one or more parentheses of the symbols can be omitted on condition that the symbols are interpreted without any ambiguity.
Also, a regular transformation in which a character string on the finite set .SIGMA. is transformed into another character string on a finite set .DELTA. is an extended concept of the regular expression which is originally defined in the present invention, and the regular transformation is a character string defined according to following definitions indicating a method for transforming a set of character strings on the finite set .SIGMA. into a set of character strings on the finite set .DELTA..
(1) In a first definition, in cases where a symbol R is a regular expression of a set of character strings on a finite set .SIGMA. and a symbol d is character strings on a finite set .DELTA., a symbol (R/d) is a regular transformation from character strings on the finite set .SIGMA. to character strings on the finite set .DELTA., characterized in that a set of character strings R on the finite set .SIGMA. is transformed into another set {d} of character strings d on the finite set .DELTA. and another set of other character strings on the finite set .SIGMA. is transformed into the empty set on the finite set .DELTA..
(2) In a second definition, in cases where symbols (R/d), (S/e) respectively are a regular transformation from character strings on the finite set .SIGMA. to character strings on the finite set .DELTA., a symbol ((R/d)+(S/e)) is a regular transformation from character strings on the finite set .SIGMA. to character strings on the finite set .DELTA., characterized in that a set of character strings on the finite set .SIGMA. not indicated by S but indicated by R is transformed into the set {d} of character strings d on the finite set .DELTA., a set of character strings on the finite set .SIGMA. not indicated by R but indicated by S is transformed into the set {e} of character strings e on the finite set .DELTA., and a set of character strings on the finite set .SIGMA. indicated by R and S is transformed into the set {d,e} of character strings on the finite set .DELTA..
(3) In a third definition, in cases where symbols (R/d), (S/e) respectively are a regular transformation from character strings on the finite set .SIGMA. to character strings on the finite set .DELTA., a symbol (R/d)(S/e)) is a regular transformation from character strings on the finite set .SIGMA. to character strings on the finite set .DELTA., characterized in that a set of character strings on the finite set .SIGMA. not indicated by (RS) but indicated by R is transformed into the set {d} of character strings d on the finite set .DELTA., a set of character strings on the finite set .SIGMA. indicated by (RS) is transformed into the set {de} of character strings on the finite set .DELTA., and other sets of character strings on the finite set .SIGMA. are transformed into the empty set .phi. on the finite set .DELTA..
(4) In a fourth definition, in cases where a symbol (R/d) is a regular transformation from character strings on the finite set .SIGMA. to character strings on the finite set .DELTA., a symbol ((R/d)*) is a regular transformation equivalent to another regular transformation (--((a+d)+(R/d))+(R/d)(R/d))+--).
(5) In a fifth definition, other sets not defined by one of the first to fourth definitions are not the regular transformation. Also, one or more parentheses in the sets can be omitted on condition that the sets are interpreted without any ambiguity.
Because of various researches performed until now, a Robinson method in which a nondeterministic Moore machine for performing the same transformation as that expressed by a regular transformation when the regular transformation is given is efficiently constructed by performing a limited number of calculations proportional to a length of the regular transformation and a subset constructing method in which a deterministic Moore machine equivalent to a nondeterministic Moore machine given is constructed are well-known. Because the subset constructing method closely relates to the present invention, the subset constructing method is described as an example of the prior art.
The equivalence of a nondeterministic Moore machine and a deterministic Moore machine is defined as that an output string output from the nondeterministic Moore machine is the same as that output from the deterministic Moore machine when an arbitrary input string is input to the machines. In this case, a deterministic Moore machine DMO=(Q',.SIGMA.,.DELTA.',.delta.',.lambda.',q') equivalent to a nondeterministic Moore machine NMO=(Q,.SIGMA.,.DELTA.,.delta.,.lambda.,q) given can be constructed as follows.
A state set Q' is defined as a set including all of subsets of a set Q as elements, and an initial state q' is set to {q}. An output set .DELTA.' is defined as a set including all of subsets of a set .DELTA. as elements, and a value of an output function .lambda.'({q1, - - - ,qN)) is defined as .lambda.(q1) U--U .lambda.(qN). A set .SIGMA. indicating an input from the outside in the deterministic Moore machine is used in common with the nondeterministic Moore machine. A value of a state-transition function .delta.'({q1, - - - ,qN), c) for arbitrary elements {q1, - - - ,qN) of the state set Q' and an arbitrary element c of the set .SIGMA. is defined as .delta.(q1,c) U--U .delta.(qN,c). The equivalence of the nondeterministic Moore machine and the deterministic Moore machine constructed according to the above definitions can be easily proved according to an induction as to a length of an input string given from the outside.
Next, an example of a conventional automatic product inspection system in which a constructing method of the deterministic Moore machine described above is used is described.
FIG. 1 is a block diagram indicating a configuration of a conventional automatic product inspection system.
As shown in FIG. 1, a conventional automatic product inspection system 11 comprises a first sensor 12 for detecting one of first features of a product conveyed on a conveyer every prescribed time and outputting a value "0" or "1" every prescribed time, a second sensor 13 for detecting one of second features of the product every prescribed time and outputting a value "0" or "1" every prescribed time, a deterministic Moore machine constructing unit 14 for producing pieces of DMO data of a deterministic Moore machine according to pieces of NMO data of a nondeterministic Moore machine input from an external equipment (not shown), a control unit 15 composed of an electronic circuit for producing pieces of control data corresponding to a final state of the deterministic Moore machine which is determined according to the DMO data produced in the deterministic Moore machine constructing unit 14 and the values time-sequentially transferred from the first and second sensors 12, 13 as a finite input set, and a sealing robot 16 for sealing the product in cases where pieces of control data indicating that the product is a non-defective product are produced in the control unit 15.
In the above configuration, a constructing method of a deterministic Moore machine performed in the deterministic Moore machine constructing unit 14 to use the deterministic Moore machine in the control unit 15 for the purpose of moving the sealing robot 16 is described. Supposing that the sealing robot 16 is moved according to the control data produced from the NMO data of the nondeterministic Moore machine, a state-transition view of the nondeterministic Moore machine is shown in FIG. 2. In FIG. 2, S.sub.0 denotes an initial state from which the inspection of each of the products is started. An external input from the first sensor 12 to the control unit 15 is indicated by a symbol A1 corresponding to a value "1" or another symbol A0 corresponding to a value "0". An external input from the second sensor 13 to the control unit 15 is indicated by a symbol B1 corresponding to a value "1" or another symbol B0 corresponding to a value "0". An input .alpha. to the nondeterministic Moore machine is indicated by the combination of the external inputs such as A0B0, A0B1, A1B0 or A1B1. In cases where an input .alpha. takes a state of the nondeterministic Moore machine from a current state to the empty set (or in cases where any transition of the nondeterministic Moore machine from a current state for an input is not defined), a current product is judged as a defective product in the control unit 15, and a succeeding product is inspected. In cases where a series of inputs takes a state of the nondeterministic Moore machine from the initial state S.sub.0 to a final state S.sub.5 marked by double circles, a current product is judged as a non-defective product in the control unit 15, and the current product is sealed by the sealing robot 16.
However, because the nondeterministic Moore machine is directly used, an input takes a state of the nondeterministic Moore machine from a current state to a plurality of states. For example, an input A1B0 takes a state of the nondeterministic Moore machine from the initial state to next states S.sub.1 and S.sub.2. Therefore, the control unit 15 is difficult to be composed of an electronic circuit in cases where the control unit 15 is operated according to the state-transition of the nondeterministic Moore machine shown in FIG. 2.
FIG. 3 is a state table showing a process for constructing a deterministic Moore machine from the nondeterministic Moore machine shown in FIG. 2 according to the subset constructing method, and FIG. 4 is a state-transition view of the deterministic Moore machine constructed according to the process shown in FIG. 3.
In the subset constructing method, the correspondence between a plurality of nondeterministic states (or a plurality of subsets of states) and a deterministic state is determined, the state-transition of the nondeterministic Moore machine from a plurality of subsets of states for a series of inputs given from the outside is examined, and a state-transition of the deterministic Moore machine is constructed. For example, as shown in FIG. 3, an input A0B1 takes a state of the deterministic Moore machine from a current state t.sub.0 ={S.sub.0 } to a next state t3={S.sub.2 }, an input A1B0 takes a state of the deterministic Moore machine from a current state t.sub.0 ={S.sub.0 } to a next state t2={S.sub.1,S.sub.2 }, and each of inputs A1B1, A0B0 takes a state of the deterministic Moore machine from a current state to={S.sub.0 } to the empty state t1=.phi..
Therefore, as shown in FIG. 4, because the state-transition of the deterministic Moore machine from a current state to a next state is defined for all types of inputs, the control unit 15 can be composed of an electronic circuit in cases where the control unit 15 is operated according to the state-transition of the deterministic Moore machine shown in FIG. 4. For example, the control unit 15 is composed of a programmable circuit device such as a programmable integrated circuit, a field programmable gate array or the like or a micro-computer. Also, a software for automatically producing a program required to operate the programmable device from the deterministic Moore machine shown in FIG. 4 is prepared in most of the programmable devices, and a design of the control circuit is broadly performed by utilizing a model of the finite-state machine as a method for expressing a circuitry of the control circuit at higher abstraction than a circuit diagram of the control circuit.
The finite-state machine can be broadly applied as various types of pattern-matching machines as well as the various control systems. In detail, a plurality of elements composing a piece of referential pattern-matching data are given to a pattern-matching machine in order as a series of inputs given from the outside. The referential pattern-matching data denotes a piece of data which should be examined. Thereafter, a series of symbols or numerals designating the detected pattern is output just after the pattern-matching data agreeing with the detected pattern is input to the pattern-matching machine. That is, the referential pattern-matching data is transformed according to the regular transformation, a nondeterministic Moore machine is constructed according to the referential pattern-matching data transformed, a deterministic Moore machine is constructed according to the nondeterministic Moore machine, and a pattern-matching operation is performed by utilizing the deterministic Moore machine. Though the pattern matching operation can be performed by utilizing the nondeterministic Moore machine, in cases where the referential pattern-matching data is long, in other words in cases where the number of elements composing the referential pattern-matching data is large, the pattern matching operation utilizing the deterministic Moore machine can be performed at a shorter time.
In general, when a length of the referential pattern-matching data is expressed by a symbol N and a length of the regular transformation (or a length of a character string) is expressed by a symbol M, a processing time proportional to NM is required in case of the pattern matching operation utilizing the nondeterministic Moore machine. In contrast, a processing time proportional to N is required at the most in case of the pattern matching operation utilizing the deterministic Moore machine. However, another processing time proportional to 2.sup.M is required to construct the deterministic Moore machine from the nondeterministic Moore machine. Accordingly, in cases where the referential pattern-matching data is long (or N is large), a processing time required for the pattern matching operation utilizing the deterministic Moore machine can be shortened as compared with the pattern matching operation utilizing the nondeterministic Moore machine.
An example of a conventional pattern-matching system in which a constructing method of the conventional pattern-matching machine described above is used is described.
In the conventional pattern-matching machine, a plurality of referential character strings desired to be found out can be simultaneously collated with character strings of a stored document by scanning the character strings of the stored document once, and a referential pattern indicated by a referential character string desired to be found out can be specified according to the regular expression.
FIG. 5 is a block diagram of a conventional pattern-matching system which is a portion of a conventional document retrieving system.
As shown in FIG. 5, a conventional pattern-matching system 21 comprises an input document memory 22 for storing character strings of an input document and reading out characters of the character strings one by one, a DMO constructing unit 23 for receiving a plurality of referential character strings desired to be found out and pieces of NMO data of a nondeterministic Moore machine input from an external equipment (not shown) and producing pieces of DMO data from the NMO data, a state number table memory 24 composed of a random access memory for storing a plurality of state numbers respectively indicating a partial matching condition between the input document and the referential character strings in a two-dimensional table in which the state numbers and character codes of the input document are listed, a state number register 25 for recording a state number output from the state number table memory 24, and an operation number table memory 26 for storing a plurality of operation numbers indicating types of operations other than the pattern matching operation performed in pattern-matching system 21 and outputting an operation number according to the state number output from the state number register 25.
In the state number table memory 24, a state-transition table (for example shown in FIG. 3) of the deterministic Moore machine calculated to satisfy pattern matching conditions represented by the referential character strings. The pattern matching conditions are specified according to the regular transformation. For example, a referential character string abcd is shown in FIG. 6. In FIG. 6, [ a] denotes all characters other than the character a, a symbol ".vertline." in "x...vertline.x...vertline.x...vertline.x...vertline.x.." denotes a logic OR, and a symbol A denotes an output. Therefore, in cases where a referential character string abcd and pieces of NMO data are input to the DMO constructing unit 23, character strings of the input document abcd, [ a]bcd, a[ b]cd, ab[ c]d and abc[ d] satisfy the pattern matching conditions, and each of the character strings is successfully pattern-matched with the referential character string abcd in the deterministic Moore machine constructed to fit the referential character string abcd before the output A informing of the pattern matching is output.
In the above configuration, the operation of the conventional pattern-matching system 21 is described.
Before a pattern matching operation is performed, a plurality of referential character strings desired to be found out and pieces of NMO data of a nondeterministic Moore machine are input from an external equipment to the DMO constructing unit 23. The NMO data indicates a state-transition in the nondeterministic Moore machine and includes one or more types of operations to be performed when a pattern matching is successfully achieved. Thereafter, pieces of DMO data are produced from the NMO data and are stored in the state number table memory 24 and the operation number table memory 26.
Thereafter, character strings of an input document are stored in the input document memory 22 after the input document memory 22 is initialized, and a remarked character of the input document is set to a head portion of the input document. Also, the state number register 25 is initialized, and a state number of a current state is initially set to zero. Also, the pattern matching conditions are stored in the state number table memory 24 and the operation number table memory 26.
Thereafter, a retrieving address is determined according to a state number of a current state output from the state number register 25 and a character number of a remarked character of the input document output from the input document memory 22, and a next state listed at the retrieving address of the two-dimensional table is determined in the state number table memory 24. Thereafter, the next state is replaced with the current state recorded in the state number register 25. That is, the next state is regarded as a current state newly defined. For example, character numbers of characters of the input document range from 0 to 65535, state numbers in the state number table memory 24 range from 0 to 8191, and addresses of the two-dimensional table in the state number table memory 24 are sent through twenty-nine address lines. The state numbers are sent through lower thirteen address lines, and the character numbers are sent through upper sixteen address lines.
Thereafter, an operation number stored in the operation number table memory 26 is determined according to the state number recorded in the state number register 25, and an additional operation indicated by the operation number is performed. For example, a position of the remarked character in the input document specified in the input document memory 22 is recorded as an additional operation. Thereafter, the remarked character is replaced with a lower character of the input document adjacent to the remarked character. Thereafter, a next state is determined in the same manner according to a current state and a character number of a remarked character newly determined, and an additional operation corresponding to the next state is performed. The operation for determining a next state and an additional operation corresponding to the next state are repeated until a patter matching operation is stopped according to the additional operation or a final character of the input document is scanned as a remarked character, and the pattern matching operation of the input document is finished.
An example of the NMO data and the DMO data is shown in FIGS. 7 to 11.
FIG. 7 is a state-transition table of the nondeterministic Moore machine constructed to satisfy the pattern matching conditions expressed in regular expression shown in FIG. 6 according to a Robinson method, FIG. 8 is a state-transition view of the nondeterministic Moore machine constructed to satisfy the pattern matching conditions expressed in the regular expression shown in FIG. 6 according to the Robinson method, FIGS. 9(a), 9(b) shows a process for constructing the deterministic Moore machine by utilizing the nondeterministic Moore machine, FIG. 10 is a state-transition table of the deterministic Moore machine constructed according to the process shown in FIGS. 9(a), 9(b), and FIG. 11 is a state-transition view of the deterministic Moore machine constructed according to the process shown in FIGS. 9(a), 9(b).
In FIG. 7, the state numbers 1 to 17 of the states t1 to t17 are listed in a state column, an output having a value A is listed in an output column, state numbers of next states for each of inputs a, b, c and d are listed in a next state column, and state numbers of next states for an input $ denoting characters other than a, b, c and d are listed in the next state column. For example, as shown in FIGS. 7 and 8, an input a takes a state of the nondeterministic Moore machine from the state t1 to next states t1,t3,t9,t12 and t15, an input 5 takes a state of the nondeterministic Moore machine from the state t1 to next states t1 and t6, and an input $ takes a state of the nondeterministic Moore machine from the state t1 to next states t1 and t6.
In FIGS. 9(a), 9(b), "DMO.sub.-- state(i): {q1,q2, - - - ,qm)" denotes that the i-th state of the deterministic Moore machine corresponds to a set having states q1,q2, - - - ,qm of the nondeterministic Moore machine as elements. "DMO.sub.-- goto ({i},"x")={p1, - - - ,pn) (j)" denotes that the input x takes a state of the deterministic Moore machine from a current state having a state number i to a next state having a state number j which corresponds to a set having states p1, - - - ,pn of the nondeterministic Moore machine as elements.
In FIG. 10, the state numbers 1 to 18 of the states t1 to t18 are listed in a state column, an output having a value A is listed in an output column, state numbers of next states for each of inputs a, b, c and d are listed in a next state column, and state numbers of next states for an input $ denoting characters other than a, b, c and d are listed in the next state column. The number of transitions is summed up to sixty-seven in cases where a transition between the same states is counted up.
As is described above, the deterministic Moore machine can be applied for various fields such as a control system and a pattern-matching system, and an output can be responded for an input within a prescribed processing time regardless of the complexity of the deterministic Moore machine.
2.2. Problems to be Solved by the Invention
However, there is a first drawback that it takes a long time to construct the finite-state machine according to the constructing method of the deterministic Moore machine. Also, there is a second drawback that a size of the finite-state machine (or a size of a state-transition table in an actual applied system) is large. Because a processing time required to construct a large sized state-transition table is larger than that proportional to the number of effective elements included in the state-transition table, the first drawback relates to the second drawback.
In contrast, in cases where the nondeterministic Moore machine is used to obtain an output responding to an input without constructing any deterministic Moore machine, the nondeterministic Moore machine can be constructed at a short processing time, and a size of the nondeterministic Moore machine. However, in cases where the nondeterministic Moore machine is complicated, there is a drawback that the nondeterministic Moore machine cannot be operated at high speed.
Also, in cases where the nondeterministic Moore machine often passes though particular state and transition, to heighten an operational speed of the nondeterministic Moore machine, it is effective that the particular state and transition of the nondeterministic Moore machine are transformed into state and transition functioning in the same manner as those of the deterministic Moore machine. However, there is a drawback that it is difficult to transform the particular state and transition of the nondeterministic Moore machine.